// 295.数组流的中位数
package LeetcodeHot100;

import java.util.PriorityQueue;

class MedianFinder {
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;

    public MedianFinder() {
        // queMin为大顶堆，queMax为小顶堆
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        // 如果加入的数比queMin最大的小，则加入queMin
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            // 平衡两个堆
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        } else {
            // 如果大于queMin的最大值，则加入queMax并进行平衡
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }

    public double findMedian() {
        // 根据是否平衡判断数量的奇偶
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}
